/*
 * @lc app=leetcode.cn id=47 lang=golang
 *
 * [47] 全排列 II
 */

// @lc code=start
func permuteUnique(nums []int) [][]int {
	tmp := make([]int, 0)
	res := make([][]int, 0)
	backing(nums, &tmp, &res)
	return res

}

func backing(nums []int, tmp *[]int, res *[][]int) {
	if len(nums) == 0 {
		t := make([]int, len(*tmp))
		copy(t, *tmp)
		*res = append(*res, t)
	}

	isRecur := make(map[int]struct{})
	for i := 0; i < len(nums); i++ {
		if _, ok := isRecur[nums[i]]; ok {
			continue
		}
		*tmp = append(*tmp, nums[i])
		isRecur[nums[i]] = struct{}{}
		tnums := make([]int, i)
		copy(tnums, nums)
		tnums = append(tnums, nums[i+1:]...)
		backing(tnums, tmp, res)
		*tmp = (*tmp)[:len(*tmp)-1]
	}
	return
}

// @lc code=end

